#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<numeric>
#include<stack>
using namespace std;

//搜索：深度（栈，往深度方向遍历）和广度
//695 给定一个二维的0-1矩阵，0表示海洋，1表示陆地，单独的或相邻的陆地可以形成岛屿，每个格子只与上下左右四个格子相邻。
//求最大的岛屿面积


//使用栈
vector<int> direction{ -1, 0, 1, 0, -1 }; //这里的方向很有讲究
int MaxAreaOfIsLand(vector<vector<int>>& grid)
{
	//思路：每个点都要去找自己、然后上下左右，并且上下左右还是陆地时，继续每个点扩散
	//m、n对应长和宽，
	int m = grid.size();
	int n = m ? grid[0].size() : 0;
	int local_area, area = 0, x, y;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; ++j)
		{
			if (grid[i][j]) //说明此时访问的点是陆地
			{
				local_area = 1;
				grid[i][j] = 0; //如果置为0，那我下一次访问不到，可行吗，可以的，因为只要和我相邻的，我都可以访问一遍的，下次就不需要这么重复算了
				stack<pair<int, int>> island;
				island.push({ i,j });
				while (!island.empty())
				{
					//开始遍历上下左右，如果是则继续把当前坐标放入栈里面
					std::pair<int,int> element = island.top();
					int x1 = element.first;
					int y1 = element.second;

					island.pop();
					for (int k = 0; k < 4; k++)
					{
						x = x1 + direction[k];
						y = y1 + direction[k + 1];
						if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
						{
							grid[x][y] = 0;
							island.push({ x,y });
							++local_area;
						}
					}

				}
				area = max(area, local_area);
			}
		}
	}

	return area;

}